沉下心来分析HashMap的源码（四）红黑树的插入
理解了2-3树和红黑树的对应的关系，再去梳理红黑树的插入和删除操作，就会更加的容易理解和记忆一点。
红黑树的插入操作
情况1
当为Null树的时候，插入第一个节点：
节点设置为根节点，设置为黑色，如下图所示：
情况2
存在父节点的情况下，插入节点，分为两种情况：2-3树上面就是有2节点形成3节点的过程。 2.1 插入的是左节点，也就是比父节点要小，直接的插入即可,但是需要考虑着色的问题。如图：
2.2 如果插入的节点比父节点大，就需要变换顺序，外加改变颜色了，如下图：
其中的坐旋转，使用文字描述为：
左旋： 右节点（right）和其父节点（right-parent）进行交换，交换的过程中，right-parent 的右分支被强制的叉开，所以把right的左孩子（right-left）放到了right-parent 的右分支，然后把right-parent 放到了right的左孩子上。
图片的描述为：
代码描述为：
/** From CLR
* 旋转节点：为 p.right
* 方法的输入的参数为 旋转子树的根节点，可以理解为图中的node节点
* */
private void rotateLeft(Node p) {
if (p != null) {
// p的右节点即是旋转上升的节点，然后旋转上升后，该节点的左节点为P，原来的左节点，这是为p的右节点
Node r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
// 设置循转节点的父节点，以及P原来父节点的指向的设置
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
//旋转节点为右节点，原来的左孩子设置为P
r.left = p;
p.parent = r;
}
}
情况3
在父节点存在的情况下，如果左孩子的左孩子一直插入的情况下，如下图所示
这个时候就是右旋的操作，具体的文字描述为：
右旋： 左节点（left）和其父节点（left-parent）进行交换，交换的过程中，left-parent 的左分支被强制的叉开，所以把left的右孩子（left-right）放到了left-parent 的左分支，然后把left-parent 放到了left的左孩子上。
具体的图示如下：
具体的代码示例为：
/** From CLR
* 该方法的参数，并不是被旋转的节点，而是调整子树的根节点，可以理解为图中的node节点
* */
private void rotateRight(Node p) {
if (p != null) {
// p的左节点设置为 原来左节点的右子树
Node l = p.left;
p.left = l.right;
if (l.right != null)
l.right.parent = p;
// 旋转过程中父节点的设置，上升节点的父节点以及原来父节点的指向的设置
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else
p.parent.left = l;
// 最后右节点和p旋转后父节点的设置
l.right = p;
p.parent = l;
}
}
情况4：
特殊的情况下，如：红色的右节点下插入左孩子，或者红色的左节点下，插入右孩子。
具体的情况的一种如下图所示：
针对这种情况，第一步我们可以通过一次左旋转，变成我们熟悉的情况3.具体的操作如下图所示：
插入的情况总结
具体的操作分为三种：左旋，右旋，变色
具体的情况如下图所示：
具体的代码如下：
public int put(K key) {
Node t = root;
if (t == null) {
root = new Node(key, null);
size = 1;
modCount++;
return 1;
}
Node parent = findParent(key);
if (parent != null) {
int cmp = this.comparator != null ? this.comparator.compare(key, parent.key)
: ((Comparable<? super K>) key).compareTo(parent.key);
Node e = new Node(key, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return 1;
} else {
return -1;
}
}
private void fixAfterInsertion(Node x) {
x.color = RED;
// x 为null，x为root的第一个节点，直接的跳走
/**
* 如果x parent 节点为黑，那么x 为红，直接的跳过即可。
* */
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Node uncle = rightOf(parentOf(parentOf(x)));
if (colorOf(uncle) == RED) {
// 图三
setColor(parentOf(x), BLACK);
setColor(uncle, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
// uncle 节点为黑或者uncle 节点为null
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
/**
* 这个操作，非常的有意思，按照左旋方法的定义，参数应该是旋转子树的根节点，但是这个传入的是旋转节点
* 然后，就变成了：x右节点和x交换位置，并且在交换位置的过程中，x有右节点变为了左节点。
* 图②
* */
rotateLeft(x);
}
// 调整颜色，当前节点为红色节点，是定死的。所以把父节点设为黑，爷节节点设置为红
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
// x 为left节点，进行右旋
// 图①
rotateRight(parentOf(parentOf(x)));
}
} else {
Node uncle = leftOf(parentOf(parentOf(x)));
if (colorOf(uncle) == RED) {
setColor(parentOf(x), BLACK);
setColor(uncle, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}